
public class criarGrafo {
	private final int MAX_NO = 20;
	private final int INFINITO = 1000000;
	private No noList[];
	private int adjMat[][];
	private int nNo;
	private int nNoArvore;
	private Aresta sCaminho[];
	private int NoAtual;
	private int DistAteNoAtual;
	public criarGrafo(){
		noList = new No[MAX_NO];
		adjMat = new int[MAX_NO][MAX_NO];
		nNo = 0;
		nNoArvore = 0;
		for(int j=0; j<MAX_NO; j++)
			for(int k=0; k<MAX_NO; k++)
				adjMat[j][k] = INFINITO;
		sCaminho = new Aresta[MAX_NO];
		
	}
	public void addNo(char rot){
		noList[nNo++] = new No(rot);
	}
	public void addAresta(int inicio, int fim, int peso){
		adjMat[inicio][fim] = peso;
	}
	public void caminho(){
		int inicioArvore = 0;
		noList[inicioArvore].ok = true;
		nNoArvore = 1;
		for(int j=0; j<nNo; j++){
			int tempDist = adjMat[inicioArvore][j];
			sCaminho[j] = new Aresta(inicioArvore, tempDist);
		}
		while(nNoArvore < nNo){
			int indexMin = getMin();
			int minDist = sCaminho[indexMin].distancia;
			if (minDist == INFINITO){
				System.out.println("Erro, No nao pode ser alcancado...");
				break;
			}
		
			else{
				NoAtual = indexMin;
				DistAteNoAtual = sCaminho[indexMin].distancia;
				
			}
			noList[NoAtual].ok = true;
			nNoArvore++;
			ajusta_sCaminho();
		}
		mostraCaminho();
		nNoArvore = 0;
		for(int j=0; j<nNo; j++)
			noList[j].ok = false;	
	}
	public int getMin(){
		int minDist = INFINITO;
		int indexMin = 0;
		for(int j=1; j<nNo; j++){
			if(!noList[j].ok && sCaminho[j].distancia < minDist){
				minDist = sCaminho[j].distancia;
				indexMin = j;
			}
		}
		return indexMin;
	}
	public void ajusta_sCaminho(){
		int coluna = 1;
		while(coluna < nNo){
			if(noList[coluna].ok){
				coluna++;
				continue;
			}
			int atualValor = adjMat[NoAtual][coluna];
			int inicioValor = DistAteNoAtual + atualValor;
			int sCaminhoDist = sCaminho[coluna].distancia;
			if(inicioValor < sCaminhoDist){
				sCaminho[coluna].parenteNo = NoAtual;
				sCaminho[coluna].distancia = inicioValor;
			}
			coluna++;
		}
	}
	public void mostraCaminho(){
		for(int j=0; j<nNo; j++){
			System.out.print(noList[j].rotulo + " = ");
			if(sCaminho[j].distancia == INFINITO)
				System.out.print("infinito");
			else
				System.out.print(sCaminho[j].distancia);
			char parente = noList[sCaminho[j].parenteNo].rotulo;
			System.out.print(" ("+parente+") ");
		}
		System.out.println("");
	}
}
